#pragma once

#include <vector>

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode() : val(0), left(nullptr), right(nullptr) { }
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) { }
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) { }
};

class Solution
{
public:
    std::vector<int> inorderTraversal(TreeNode* root)
    {
        std::vector<int> visited;
        traverse_inorder(root, visited);
        return visited;
    }

    std::vector<int> inorderTraversal2(TreeNode* root)
    {
        std::vector<int> visited;
        std::vector<TreeNode*> stack;

        while (!stack.empty() || root) {
            if (root) {
                stack.push_back(root);
                root = root->left;
            } else {
                root = stack.back();
                stack.pop_back();
                visited.push_back(root->val);
                root = root->right;
            }
        }

        return visited;
    }

private:
    void traverse_inorder(TreeNode* root, std::vector<int>& visited)
    {
        if (root == nullptr)
            return;
        traverse_inorder(root->left, visited);
        visited.push_back(root->val);
        traverse_inorder(root->right, visited);
    }
};
